package cn.itsource.arraylist;

import java.util.Arrays;

/**
 *	1. 数据结构：就是数据保存的方式。
 *
 *	2. 为什么要学习？
 *		就是为了在不同的需求下，更好的选择合适的数据类型，可以提高效率
 *
 *	3. 数据结构都有哪些？
 *			1. List 有序（存入和取出）可重复集合		
 *				1. ArrayList	基于数组，适用于查询和修改较多
 *				2. LinkedList	基于双向链表，适用于增删插
 *					Stack（栈，先进后出 FILO）
 *				3. Vector 线程安全的ArrayList
 *				
 *			2. Set	无序（存入和取出）不可重复集合
 *				1. HashSet	
 *				2. TreeSet
 *				3. LinkedHashSet
 *
 *			3. Map	键值对（Entry<Key,Value>）集合
 *				1. HashMap
 *				2. TreeMap
 *				3. LinkedHashMap
 *				4. ConcurrentHashMap
 *				5. HashTable
 *
 *			4. Queue 队列  （订单排队，任务队列）
 *				1. Queue	FIFO先进先出	
 *				2. Deque	双端队列 ，两端进出
 *					Stack	栈，FILO
 *					
 *			5. Tree 树状结构 （菜单和子菜单，上下级关系）
 *				1. 二叉树
 *						红黑树（自平衡机制，为了提高查询效率）
 *
 *				2. 多叉树
 *
 *	4. 能够保存数据的方式有哪些？
 *		1. 变量（保存一个）
 *		2. 数组（保存多个）
 *
 *	5. 需求：
 *			基于数组，查询和修改效率高，增删插效率低，适用于查询和修改多的场景
 *			
 *			1. 设计一个类可以保存多个任意类型的数据（基于Object数组）int byte Integer/Byte
 *			2. 可以任意添加任意类型的数据 void add(Object obj)
 *						version2 自动扩容
 *			3. 可以记录当前数据的个数 int size()
 *			4. 可以打印当前数据结构的对象，格式如下：[值1，值2.。。。。]
 *
 *			5. 查询指定下标的元素  Object searchByIndex(int index)
 *			6. 查询指定的元素第一次出现的位置  int searchByElement(Object ele);
 *
 *			7. 修改指定下标处的元素  void updateByIndex(int index,Object obj)
 *			8. 删除指定下标处的元素，返回删除的元素  	Object deleteByIndex(int index)
 *			9. 删除的首次出现的指定元素     void deleteByElement(Object ele)
 *			10.插入指定下标处一个指定元素 void insertByIndex(int index,Object obj)
 *					
 *			11.将对象中所有元素清空 void clear();
 *			12.可以创建指定长度的ArrayList对象
 *			13.创建一个默认长度是10的ArrayList对象
 *			14.创建一个默认长度是10，且有指定元素的ArrayList对象
 *
 *			参考StringBuilder
 *			增删改查插
 */	
public class ArrayListDemo {
	/**	1. 设计一个类可以保存多个任意类型的数据（基于Object数组）int byte Integer/Byte*/
	private Object[] value;
	
	/**当前数组中存放元素的个数，默认是0，正好是第一个元素下标*/
	private int size;
	
	/**
	 * 12.可以创建指定长度的ArrayList对象
	 * @param length
	 */
	public ArrayListDemo(int length) {
		super();
		value = new Object[length];
	}
	
	/**
	 * 13.创建一个默认长度是10的ArrayList对象
	 */
	public ArrayListDemo() {
		this(10);
	}
	
	/**
	 * 14.创建一个默认长度是10，且有指定元素的ArrayList对象
	 */
	public ArrayListDemo(Object obj) {
		this(10);
		//直接都用添加元素方法
		add(obj);
	}
	
	
	
	/**
	 * 2. 可以任意添加任意类型的数据 void add(Object obj)
	 * @param obj 添加的数据
	 */
	public void add(Object obj){
		//version2 自动扩容,再添加元素之前，必须确定当前数组长度是否大于元素个数，如果装不下就要扩容
		growArrayCapcity();
		//添加第一个元素:通过下标给数组赋值
		value[size] = obj;
		//每次添加元素，元素个数+1
		size++;
	}
	
	/**
	 * 数组扩容方法
	 * 扩容机制 *2
	 */
	private void growArrayCapcity() {
		if (size == value.length) {//扩容机制 *2
			//必须将扩容后的数组地址重新赋值给value保存
			value = Arrays.copyOf(value, value.length * 2);
		}
	}
	
	/**
	 * 3. 可以记录当前数据的个数 int size()
	 * @return
	 */
	public int size(){
		return size;
	}
	
	/**
	 * 4. 可以打印当前数据结构的对象，格式如下：[值1，值2.。。。。]
	 *  @return
	 */
	@Override
	public String toString() {
		//因为当前数组中，有空的位置，没有添加上元素，所以必须通过数组缩容来获取一个新数组，将有元素的新数组转换为字符串
		Object[] newArr = Arrays.copyOf(value,size);
		return Arrays.toString(newArr);
	}
	
	/**
	 * 5. 查询指定下标的元素  Object searchByIndex(int index)
	 * @param index
	 * @return
	 * @throws IllegalAccessException 
	 */
	public Object searchByIndex(int index) throws IllegalAccessException{
		//校验下标合法性
		checkIndex(index);//alt + shift + m  提取方法快捷键
		return value[index];
	}
	
	/**
	 * 校验下标合法性
	 * @param index
	 * @throws IllegalAccessException
	 */
	private void checkIndex(int index) throws IllegalAccessException {
		if (index > size-1 || index < 0) {
			throw new IllegalAccessException("请注意，下标范围：[0," + (size-1) + "]");//非法参数异常，给调用者提示
		}
	}
	
	/**
	 * 6. 查询指定的元素第一次出现的位置  int searchByElement(Object ele);
	 * @param ele
	 * @return
	 */
	public int searchByElement(Object ele){
		//遍历数组，将当前ele跟数组每一元素进行比较，如果相等，就返回下标，如果遍历完毕后，没有找到，就返回-1，表示未找到
		//必须先判断当前ele元素是否是一个null元素,为了避免调用equals方法的时候发生空指针异常
		if (ele == null) {
			for (int i = 0; i < size; i++) {//这里是遍历有size个元素的数组，而不是整个数组长度
				if (ele == value[i]) {
					return i;
				}
			}
		} else {
			for (int i = 0; i < size; i++) {//这里是遍历有size个元素的数组，而不是整个数组长度
				if (ele.equals(value[i])) {//这里只能是用ele.equals(),因为这里在else中，已经可以确定ele已经不是null
					return i;
				}
			}
		}
		return -1;//表示在遍历完后没有找到
	}
	
	/**
	 * 7. 修改指定下标处的元素  void updateByIndex(int index,Object obj)
	 * @param index
	 * @param obj
	 * @throws IllegalAccessException 
	 */
	public void updateByIndex(int index,Object obj) throws IllegalAccessException{
		//校验下标合法性
		checkIndex(index);
		value[index] = obj;
	}
	
	/**
	 * 8. 删除指定下标处的元素，返回删除的元素  	Object deleteByIndex(int index)
	 * @param index
	 * @return
	 * @throws IllegalAccessException 
	 */
	public Object deleteByIndex(int index) throws IllegalAccessException{
		//校验下标合法性
		checkIndex(index);
		//画图
		//声明一个变量将要删除的元素保存
		Object delete = value[index];
		//将数组删除指定下标处元素
		System.arraycopy(value, index+1,value,index, size-index-1);//这里arraycopy方法是原生方法，是Java都用其他语言的方法，无法查看源码。但是这里已经处理的index+1 > 最后一个元素下标（size-1）的情况
		//元素个数-1
		size--;
		return delete;
	}
	
	/**
	 * 9. 删除的首次出现的指定元素     void deleteByElement(Object ele)
	 * @param ele
	 * @throws IllegalAccessException 
	 */
	public void deleteByElement(Object ele) throws IllegalAccessException{
		//调用自己的searchByElement返回ele下标
		int index = searchByElement(ele);
		//判断下标是否为负数，如果是，表示数组中没有该元素，则直接结束方法
		if (index < 0) {
			return;
		}
		//调用根据下标删除元素方法deleteByIndex
		deleteByIndex(index);
	}
	
	/**
	 * 10.插入指定下标处一个指定元素 void insertByIndex(int index,Object obj)
	 * @param index
	 * @param obj
	 * @throws IllegalAccessException 
	 */
	public void insertByIndex(int index,Object obj) throws IllegalAccessException{
		//校验下标合法性：这里情况比较特殊，如果是在最后一个位置后插入，则直接都用add方法,所以在这里判断下标范围是：[0,size]
		if (index > size || index < 0) {
			throw new IllegalAccessException("请注意，插入的元素下标范围：[0," + size + "]");//非法参数异常，给调用者提示
		}
		//校验下标合法性：这里情况比较特殊，如果是在最后一个位置后插入，则直接都用add方法
		if (index == size) {//size表示在最后一个位置后插入元素
			add(obj);
			return;//添加完毕后，必须结束方法
		}
		//判断是否需要扩容
		growArrayCapcity();
		//画图 搞清楚需要复制几个元素和下标的几个特殊情况：第一个、最后一个。注意：必须先复制再给指定下标元素赋值。
		System.arraycopy(value, index, value, index+1, size-index);
		//给指定下标元素赋值
		value[index] = obj;
		//元素个数+1
		size++;
	}
			
	/**
	 * 11.将对象中所有元素清空 void clear();
	 */
	public void clear(){
		//将vlaue重新赋值即可
		value = new Object[10];
		//元素个数重置为0
		size = 0;
	}
}
